package main

import (
	"fmt"
)

/**
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]





链接：https://leetcode-cn.com/problems/permutations

解析:
回溯法
1.确定实现大方向--回溯
2.编写回溯模板，横向扩展(for),增项扩展(backtrace)，写回溯结束条件并保存搜索到的结果
3.返回结果

优质解析1:
https://leetcode-cn.com/problems/permutations/comments/1011349

优质解析2:
https://www.youtube.com/watch?v=43w8tXWKSLw&t=920s
*/
func main() {
	res := permute([]int{1, 2, 3})
	fmt.Println(res)
}

func permute(nums []int) [][]int {
	res, t, m := [][]int{}, []int{}, make(map[int]bool)
	permuteHelper(&res, nums, t, m)
	return res
}

func permuteHelper(res *[][]int, nums []int, t []int, m map[int]bool) {
	if len(t) == len(nums) {
		//重点 slice是引用类型 不可以直接赋值 否则下次修改会影响之前res中以保存的结果 这里一定要拷贝
		temp := make([]int, len(t))
		copy(temp, t)
		*res = append(*res, temp)
		return
	} else {
		for i := 0; i < len(nums); i++ { // 每次循环都是从头开始执行,每次开启循环其实就是选择一位数字
			if _, ok := m[i]; !ok {
				m[i] = true
				t = append(t, nums[i])
				permuteHelper(res, nums, t, m)
				t = t[:len(t)-1]
				delete(m, i)
			}
		}
	}
}

func permute(nums []int) [][]int {
	res := [][]int{}
	list := []int{}
	var helper func(m map[int]bool)
	helper = func(m map[int]bool) {
		if len(list) == len(nums) {
			res = append(res, append([]int{}, list...))
			return
		}

		for i := 0; i < len(nums); i++ {
			list = append(list, nums[i])
			m[i] = true
			helper(m)
			list = list[:len(list)-1]
			delete(m, i)
		}
	}
	helper(make(map[int]bool))
	return res
}
